
struct Solution {}

impl Solution {
  pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
  let l = nums.len();
  let mut increase = vec![0; l];
  let mut decrease = vec![0; l];
  let mut re_increase = vec![0; l];
  let mut re_decrease = vec![0; l];
  let mut in_stack: Vec<usize> = vec![];
  let mut de_stack: Vec<usize> = vec![];
  for i in 0..l {
    while !in_stack.is_empty() && nums[i] > nums[in_stack[in_stack.len() - 1]] {
      in_stack.pop().unwrap();
    }
    if in_stack.is_empty() {
      increase[i] = i + 1;
    } else {
      increase[i] = i - in_stack[in_stack.len() - 1];
    }
    in_stack.push(i);
    while !de_stack.is_empty() && nums[i] <= nums[de_stack[de_stack.len() - 1]] {
      de_stack.pop().unwrap();
    }
    if de_stack.is_empty() {
      decrease[i] = i + 1;
    } else {
      decrease[i] = i - de_stack[de_stack.len() - 1];
    }
    de_stack.push(i);
  }
  // println!("{:?} {:?}", increase, decrease);
  in_stack.clear();
  de_stack.clear();
  for i in (0..l).rev() {
    while !in_stack.is_empty() && nums[i] >= nums[in_stack[in_stack.len() - 1]] {
      in_stack.pop().unwrap();
    }   
    if in_stack.is_empty() {
      re_increase[i] = l - i;
    } else {
      re_increase[i] = in_stack[in_stack.len() - 1] - i;
    }
    in_stack.push(i);
    while !de_stack.is_empty() && nums[i] < nums[de_stack[de_stack.len() - 1]] {
      de_stack.pop().unwrap();
    }
    if de_stack.is_empty() {
      re_decrease[i] = l - i;
    } else {
      re_decrease[i] = de_stack[de_stack.len() - 1] - i;
    } 
    de_stack.push(i);
  }
  // println!("{:?} {:?}", re_increase, re_decrease);
  (0..l).map(|i| {
    let p = increase[i] * re_increase[i];
    let n = decrease[i] * re_decrease[i];
    nums[i] as i64 * (p - n) as i64 
  }).sum::<i64>()
  }
}